#include <stdio.h>
#include <stdlib.h>
#include <time.h>

typedef int ElemType;
typedef struct {
    ElemType lenth;
    ElemType *str;
} SSTable;

void array_print(SSTable T) {
    for (int i = 0; i < T.lenth; i++) {
        printf("%3d", T.str[i]);
    }
    printf("\n");
}

int compare(const void *left, const void *right) {
    return *(int *) (left) - *(int *) (right);
}

void ST_Init(SSTable &T, int len) {
    T.lenth = len;
    T.str = (ElemType *) malloc(sizeof(ElemType) * T.lenth);
    int i;
    srand(time(NULL));
    for (i = 0; i < T.lenth; i++) {
        T.str[i] = rand() % 100;//随机数范围（0~99）
    }
}

void swap(int &a, int &b) {
    a ^= b;
    b ^= a;
    a ^= b;
}

//冒泡排序
//往往需要两层循环
//优先去写内层循环，再写外层循环
void BubbleSort(ElemType *str, int lenth) {
    bool flag;
    for (int i = 0; i < lenth - 1; i++) {//控制的是有序数的数目
        for (int j = lenth - 1; j > i; j--) {//内层控制比较和交换
            flag=false;
            if (str[j - 1] > str[j]) {
                swap(str[j - 1], str[j]);
                flag = true;
            }
        }
        if(!flag){//如果一趟比较没有发生任何交换，说明数组有序，提交结束排序
            return;
        }
    }
}

int main() {
    SSTable T;
    ST_Init(T, 10);

    array_print(T);
//    qsort(T.str, 10, sizeof(int), compare);
    BubbleSort(T.str, 10);
    array_print(T);
    return 0;
}
